<TITLE>prob001: car sequencing</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob001: car sequencing</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.scs.leeds.ac.uk/bms/home.html">
          <B>Barbara Smith</B></A> 
          <ADDRESS><a href="mailto:bms@scs.leeds.ac.uk">
          bms@scs.leeds.ac.uk</a></ADDRESS>
</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

<TT>


A  number of cars are to be produced; they are not identical,
because different options are available as variants on the basic model.
The assembly line has
different stations which install the various  options (air-conditioning,
sun-roof, etc.). These stations
have been designed to handle at most  a certain
percentage of the cars passing along the assembly line.
Furthermore, the cars requiring a certain option must not be bunched
together, otherwise the station will not be able to cope.
Consequently, the cars must be arranged in a sequence so that the capacity
of each station is never exceeded.
For instance, if a particular station can only cope with at most half
of the cars passing along the line, the sequence must be built so that at
most 1 car in any 2 requires that option.

<P>

In all the data files, it is assumed that there are  five options, with the
capacities given below.  


<P>
                                                                                

<CENTER>
<TABLE>
<TR> 
# option data:  for each option,  its capacity, <BR>
# e.g. at most 1 car out of any 2 for option 1 <TR>
<TD> 1 <TD> 2
<TR>
<TD> 2 <TD> 3
<TR>
<TD> 1 <TD> 3
<TR>
<TD> 2 <TD> 5
<TR>
<TD> 1 <TD> 5
<TR>
</TABLE>
</CENTER>
                                                                                
<P>

The format of the data files specifying the individual cars to be
sequenced is as shown below.  

<P>
<CENTER>
<TABLE>
 # Format of data: 
<BR>
# First line: number of cars; number of options (5); number  of classes.
<BR>
# Then for each class: index no.; no. of cars in this class; 
<BR>
# for each option, whether or not this class requires it (1 or 0) 
<BR>
# (This is the example given in Dincbas et al., ECAI88)
<TR>
<TD> 10 <TD>  5 <TD>  6 <TR>
<TD> 0 <TD> 1 <TD> 1 <TD> 0 <TD> 1 <TD> 1 <TD> 0 <TR>
<TD> 1 <TD> 1 <TD> 0 <TD> 0 <TD> 0 <TD> 1 <TD> 0 <TR>
<TD> 2 <TD> 2 <TD> 0 <TD> 1 <TD> 0 <TD> 0 <TD> 1 <TR>
<TD> 3 <TD> 2 <TD> 0 <TD> 1 <TD> 0 <TD> 1 <TD> 0 <TR>
<TD> 4 <TD> 2 <TD> 1 <TD> 0 <TD> 1 <TD> 0 <TD> 0 <TR>
<TD> 5 <TD> 2 <TD> 1 <TD> 1 <TD> 0 <TD> 0 <TD> 0 <TR>
</TABLE>
</CENTER>
                                                                                
<P>

A valid sequence for this set of cars is:

<CENTER>
<TABLE>
<TR> 
<TD> Class <TD>  Options req. <TR>
<TD> 0  <TD>     1 0 1 1 0 <TR>
<TD> 1  <TD>     0 0 0 1 0 <TR>
<TD> 5  <TD>     1 1 0 0 0 <TR>
<TD> 2  <TD>     0 1 0 0 1 <TR>
<TD> 4  <TD>     1 0 1 0 0 <TR>
<TD> 3  <TD>     0 1 0 1 0 <TR>
<TD> 3  <TD>     0 1 0 1 0 <TR>
<TD> 4  <TD>     1 0 1 0 0 <TR>
<TD> 2  <TD>     0 1 0 0 1 <TR>
<TD> 5  <TD>     1 1 0 0 0 <TR>
</TABLE>
</CENTER>
                                                                                
<P>





</TT>


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


